class Node:
    def __init__(self,val=0,next=None):
        self.val=val 
        self.next=next 

def solve(head):
    if not head or not head.next: return head
    slow,fast=head,head.next
    while fast and fast.next: #**
        slow,fast=slow.next,fast.next.next
    
    mid,slow.next=slow.next,None #**
    left,right=solve(head),solve(mid) #**
    dummy=Node()
    cur,cur1,cur2=dummy,left,right 
    while cur1 and cur2:
        if cur1.val<=cur2.val: 
            cur.next=cur1
            cur1=cur1.next 
        else:
            cur.next=cur2 
            cur2=cur2.next 
        cur=cur.next
    if cur1: cur.next=cur1 
    if cur2: cur.next=cur2 
    return dummy.next 

def print1(head):
    cur=head
    while cur:
        print(cur.val)
        cur=cur.next 

def build(lst):
    if len(lst)==0: return None
    head0=Node(lst[0])
    cur=head0
    for i in range(1,len(lst)):
        cur.next=Node(lst[i])
        cur=cur.next 
    return head0 

head=build([4,2,1,3])
print1(head)
print()
print1(solve(head))



